Задача #M034F

Tadqiqotchi Fedya bir kuni bir shahardan boshqasiga borish haqida o'ylab qoldi. Ammo u unchalik ham boy bo'lmagani uchun sizdan yordam so'ramoqchi qaysi shahardan qaysi shaharga borsa eng qimmatga tushadi shuni bilmoqchi. Har bitta shaharga kirish uchun badal mavjud.Ba'zi shaharlarda bu qiymat manfiy chunki ular turizmni rivojlantirishmoqchi. Bunda i shahardan j shaharga borish narxi

|a[i] - a[j]| + |i - j|
a[i] - i-shaharga kirish badali.

Bunda indekslash noldan boshlanadi.

Fedyaga bu narxni topishda yordam bering.

Birinchi qatorda n shaharlar soni. Ikkinchi qatorda esa mos ravishda n ta shaharga kirish badali.

1 <= n <= 5*(105)
-106 <= a[i] <= 106

1 ta butun son eng maksimal narx bir shahardan boshqasiga sayohat qilish uchun.